package 动态规划.背包And分组And切割问题系列;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/10/10 22:59
 */
public class lc70爬楼梯系列 {


    // f(index) 表示： 从index 开始 爬 到顶上，有多少种方式
    public int climbStairs(int n){
        return 0;
    }


    // lc746 最小花费 爬楼梯， 这种还是 改成 dp 比较好， 记忆化搜索，都点费空间
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length + 1;
         Integer dp[] = new Integer [n + 1];
        int a1 = recursion(0,cost,dp);
//        int a2 = recursion(1,cost,new Integer [n + 1]);
        return Math.min(a1,dp[1]);
    }
    // f(index) 表示 从index 开始爬楼梯的最小花费， 所以上面的调用不用调用两次， 直接 使用 dp 缓存进行查询就行了。
    public int recursion(int index,int cost[],Integer dp[]){
        if(index == cost.length){
            return 0;
        }
        if(index == cost.length - 1){
//            return cost[index];
            return dp[index] = cost[index];
        }
        if(dp[index] != null){
            return dp[index];
        }
        return  dp[index] = Math.min(recursion(index + 1,cost,dp), recursion(index + 2,cost,dp)) + cost[index];
    }

}
